package seqlist.leetcode;

/**
 * 反转链表
 * @author yuisama
 * @date 2022/04/22 20:00
 **/
public class Num206_ReverseList {
    // 1.头插法
//    public ListNode reverseList(ListNode head) {
//        ListNode dummyHead = new ListNode();
//        // 边遍历原链表，边新建节点头插入新链表
//        while (head != null) {
//            ListNode node = new ListNode(head.val);
//            node.next = dummyHead.next;
//            dummyHead.next = node;
//            head = head.next;
//        }
//        return dummyHead.next;
//    }
    // 2.迭代
//    public ListNode reverseList(ListNode head) {
//        // 边界
//        if (head == null || head.next == null) {
//            return head;
//        }
//        ListNode prev = null;
//        ListNode cur = head;
//        while (cur != null) {
//            // 暂存一下下一个要处理的结点的地址
//            ListNode next = cur.next;
//            cur.next = prev;
//            prev = cur;
//            cur = next;
//        }
//        // 当cur走到空，所有节点处理完毕，prev恰好是反转后的头节点
//        return prev;
//    }
    // 3.递归
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 暂存一下第二个节点的地址
        ListNode node = head.next;
        // 第二个节点开始的子链表反转交给子函数
        ListNode newHead = reverseList(head.next);
        // 3.拼接当前head
        node.next = head;
        head.next = null;
        return newHead;
    }
}